<!DOCTYPE html>
<html lang="zh-CN">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <meta name="generator" content="VuePress 2.0.0-beta.66">
    <style>
      :root {
        --c-bg: #fff;
      }
      html.dark {
        --c-bg: #22272e;
      }
      html, body {
        background-color: var(--c-bg);
      }
    </style>
    <script>
      const userMode = localStorage.getItem('vuepress-color-scheme');
			const systemDarkMode = window.matchMedia && window.matchMedia('(prefers-color-scheme: dark)').matches;
			if (userMode === 'dark' || (userMode !== 'light' && systemDarkMode)) {
				document.documentElement.classList.toggle('dark', true);
			}
    </script>
    <title>你好， VuePress ！</title><meta name="description" content="这是我的第一个 VuePress 站点">
    <link rel="preload" href="/assets/style-8a38cc2d.css" as="style"><link rel="stylesheet" href="/assets/style-8a38cc2d.css">
    <link rel="modulepreload" href="/assets/app-6c74e544.js"><link rel="modulepreload" href="/assets/快速幂算法 牛客小白月赛 1-C分元宵.html-6a00d92c.js"><link rel="modulepreload" href="/assets/快速幂算法 牛客小白月赛 1-C分元宵.html-41e7e00f.js"><link rel="prefetch" href="/assets/index.html-75ca5b8c.js" as="script"><link rel="prefetch" href="/assets/化学.html-bcd92d03.js" as="script"><link rel="prefetch" href="/assets/IDEA.html-ce9ad873.js" as="script"><link rel="prefetch" href="/assets/python调用idm下载.html-615c23bf.js" as="script"><link rel="prefetch" href="/assets/index.html-571c49cc.js" as="script"><link rel="prefetch" href="/assets/VuePress2x搭建.html-910a2c4e.js" as="script"><link rel="prefetch" href="/assets/WindowsTerminal.html-4a75819f.js" as="script"><link rel="prefetch" href="/assets/乱七八糟.html-0ad5c8cc.js" as="script"><link rel="prefetch" href="/assets/国内访问GitHub.html-bd9bc6eb.js" as="script"><link rel="prefetch" href="/assets/虚拟机安装凤凰OS.html-fd472c84.js" as="script"><link rel="prefetch" href="/assets/软件工程过程.html-ad186a25.js" as="script"><link rel="prefetch" href="/assets/Java.html-a9e8e4b2.js" as="script"><link rel="prefetch" href="/assets/latex.html-b66b07c2.js" as="script"><link rel="prefetch" href="/assets/Markdown.html-76abef01.js" as="script"><link rel="prefetch" href="/assets/Markdown_vuepress.html-7a108572.js" as="script"><link rel="prefetch" href="/assets/Numpy.html-742cd1c8.js" as="script"><link rel="prefetch" href="/assets/python.html-80001bc2.js" as="script"><link rel="prefetch" href="/assets/python爬虫.html-0eaf5c34.js" as="script"><link rel="prefetch" href="/assets/index.html-404afaec.js" as="script"><link rel="prefetch" href="/assets/Redis.html-3c0347e6.js" as="script"><link rel="prefetch" href="/assets/Selenium.html-dd74eb14.js" as="script"><link rel="prefetch" href="/assets/数据库.html-a9b825b9.js" as="script"><link rel="prefetch" href="/assets/数据结构_学校.html-db54f988.js" as="script"><link rel="prefetch" href="/assets/404.html-f9875e7b.js" as="script"><link rel="prefetch" href="/assets/index.html-f9be7961.js" as="script"><link rel="prefetch" href="/assets/化学.html-55546e87.js" as="script"><link rel="prefetch" href="/assets/IDEA.html-3d6ee1dc.js" as="script"><link rel="prefetch" href="/assets/python调用idm下载.html-862a9ae4.js" as="script"><link rel="prefetch" href="/assets/index.html-71e4b30e.js" as="script"><link rel="prefetch" href="/assets/VuePress2x搭建.html-69ed53cb.js" as="script"><link rel="prefetch" href="/assets/WindowsTerminal.html-d051c0b9.js" as="script"><link rel="prefetch" href="/assets/乱七八糟.html-e6e19f4d.js" as="script"><link rel="prefetch" href="/assets/国内访问GitHub.html-5a1e283c.js" as="script"><link rel="prefetch" href="/assets/虚拟机安装凤凰OS.html-3f19c5ba.js" as="script"><link rel="prefetch" href="/assets/软件工程过程.html-d5033030.js" as="script"><link rel="prefetch" href="/assets/Java.html-07b672b0.js" as="script"><link rel="prefetch" href="/assets/latex.html-139cf75a.js" as="script"><link rel="prefetch" href="/assets/Markdown.html-24c02676.js" as="script"><link rel="prefetch" href="/assets/Markdown_vuepress.html-a9f40501.js" as="script"><link rel="prefetch" href="/assets/Numpy.html-6ea20a5f.js" as="script"><link rel="prefetch" href="/assets/python.html-da27b5e1.js" as="script"><link rel="prefetch" href="/assets/python爬虫.html-22e08aed.js" as="script"><link rel="prefetch" href="/assets/index.html-25c668e6.js" as="script"><link rel="prefetch" href="/assets/Redis.html-732c58b4.js" as="script"><link rel="prefetch" href="/assets/Selenium.html-8840df78.js" as="script"><link rel="prefetch" href="/assets/数据库.html-e55ff260.js" as="script"><link rel="prefetch" href="/assets/数据结构_学校.html-cf35a9b9.js" as="script"><link rel="prefetch" href="/assets/404.html-ad53950d.js" as="script"><link rel="prefetch" href="/assets/mermaid-9e549946.js" as="script">
  </head>
  <body>
    <div id="app"><!--[--><div class="theme-container"><!--[--><header class="navbar"><div class="toggle-sidebar-button" title="toggle sidebar" aria-expanded="false" role="button" tabindex="0"><div class="icon" aria-hidden="true"><span></span><span></span><span></span></div></div><span><a href="/" class=""><img class="logo" src="/img/hero.png" alt="你好， VuePress ！"><span class="site-name can-hide">你好， VuePress ！</span></a></span><div class="navbar-items-wrapper" style=""><!--[--><!--]--><nav class="navbar-items can-hide"><!--[--><div class="navbar-item"><div class="navbar-dropdown-wrapper"><button class="navbar-dropdown-title" type="button" aria-label="编程"><span class="title">编程</span><span class="arrow down"></span></button><button class="navbar-dropdown-title-mobile" type="button" aria-label="编程"><span class="title">编程</span><span class="right arrow"></span></button><ul style="display:none;" class="navbar-dropdown"><!--[--><li class="navbar-dropdown-item"><a href="/program/Java.md" class="" aria-label="Java"><!--[--><!--]--> Java <!--[--><!--]--></a></li><li class="navbar-dropdown-item"><a href="/program/Python.md" class="" aria-label="Python"><!--[--><!--]--> Python <!--[--><!--]--></a></li><li class="navbar-dropdown-item"><!--[--><h4 class="navbar-dropdown-subtitle"><span>笔记</span></h4><ul class="navbar-dropdown-subitem-wrapper"><!--[--><li class="navbar-dropdown-subitem"><a href="/program/Markdown.html" class="" aria-label="Markdown"><!--[--><!--]--> Markdown <!--[--><!--]--></a></li><li class="navbar-dropdown-subitem"><a href="/program/latex.html" class="" aria-label="Latex"><!--[--><!--]--> Latex <!--[--><!--]--></a></li><!--]--></ul><!--]--></li><li class="navbar-dropdown-item"><a href="/program/数据库.md" class="" aria-label="数据库"><!--[--><!--]--> 数据库 <!--[--><!--]--></a></li><!--]--></ul></div></div><div class="navbar-item"><a href="/hx/化学.md" class="" aria-label="化学"><!--[--><!--]--> 化学 <!--[--><!--]--></a></div><div class="navbar-item"><a href="/others/" class="" aria-label="乱七八糟"><!--[--><!--]--> 乱七八糟 <!--[--><!--]--></a></div><div class="navbar-item"><a class="external-link" href="https://gitee.com/Francis-xsc/francis-xsc" rel="noopener noreferrer" target="_blank" aria-label="Gitee"><!--[--><!--]--> Gitee <span><svg class="external-link-icon" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path><polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg><span class="external-link-icon-sr-only">open in new window</span></span><!--[--><!--]--></a></div><!--]--></nav><!--[--><!--]--><button class="toggle-color-mode-button" title="toggle color mode"><svg style="" class="icon" focusable="false" viewBox="0 0 32 32"><path d="M16 12.005a4 4 0 1 1-4 4a4.005 4.005 0 0 1 4-4m0-2a6 6 0 1 0 6 6a6 6 0 0 0-6-6z" fill="currentColor"></path><path d="M5.394 6.813l1.414-1.415l3.506 3.506L8.9 10.318z" fill="currentColor"></path><path d="M2 15.005h5v2H2z" fill="currentColor"></path><path d="M5.394 25.197L8.9 21.691l1.414 1.415l-3.506 3.505z" fill="currentColor"></path><path d="M15 25.005h2v5h-2z" fill="currentColor"></path><path d="M21.687 23.106l1.414-1.415l3.506 3.506l-1.414 1.414z" fill="currentColor"></path><path d="M25 15.005h5v2h-5z" fill="currentColor"></path><path d="M21.687 8.904l3.506-3.506l1.414 1.415l-3.506 3.505z" fill="currentColor"></path><path d="M15 2.005h2v5h-2z" fill="currentColor"></path></svg><svg style="display:none;" class="icon" focusable="false" viewBox="0 0 32 32"><path d="M13.502 5.414a15.075 15.075 0 0 0 11.594 18.194a11.113 11.113 0 0 1-7.975 3.39c-.138 0-.278.005-.418 0a11.094 11.094 0 0 1-3.2-21.584M14.98 3a1.002 1.002 0 0 0-.175.016a13.096 13.096 0 0 0 1.825 25.981c.164.006.328 0 .49 0a13.072 13.072 0 0 0 10.703-5.555a1.01 1.01 0 0 0-.783-1.565A13.08 13.08 0 0 1 15.89 4.38A1.015 1.015 0 0 0 14.98 3z" fill="currentColor"></path></svg></button><!----></div></header><!--]--><div class="sidebar-mask"></div><!--[--><aside class="sidebar"><nav class="navbar-items"><!--[--><div class="navbar-item"><div class="navbar-dropdown-wrapper"><button class="navbar-dropdown-title" type="button" aria-label="编程"><span class="title">编程</span><span class="arrow down"></span></button><button class="navbar-dropdown-title-mobile" type="button" aria-label="编程"><span class="title">编程</span><span class="right arrow"></span></button><ul style="display:none;" class="navbar-dropdown"><!--[--><li class="navbar-dropdown-item"><a href="/program/Java.md" class="" aria-label="Java"><!--[--><!--]--> Java <!--[--><!--]--></a></li><li class="navbar-dropdown-item"><a href="/program/Python.md" class="" aria-label="Python"><!--[--><!--]--> Python <!--[--><!--]--></a></li><li class="navbar-dropdown-item"><!--[--><h4 class="navbar-dropdown-subtitle"><span>笔记</span></h4><ul class="navbar-dropdown-subitem-wrapper"><!--[--><li class="navbar-dropdown-subitem"><a href="/program/Markdown.html" class="" aria-label="Markdown"><!--[--><!--]--> Markdown <!--[--><!--]--></a></li><li class="navbar-dropdown-subitem"><a href="/program/latex.html" class="" aria-label="Latex"><!--[--><!--]--> Latex <!--[--><!--]--></a></li><!--]--></ul><!--]--></li><li class="navbar-dropdown-item"><a href="/program/数据库.md" class="" aria-label="数据库"><!--[--><!--]--> 数据库 <!--[--><!--]--></a></li><!--]--></ul></div></div><div class="navbar-item"><a href="/hx/化学.md" class="" aria-label="化学"><!--[--><!--]--> 化学 <!--[--><!--]--></a></div><div class="navbar-item"><a href="/others/" class="" aria-label="乱七八糟"><!--[--><!--]--> 乱七八糟 <!--[--><!--]--></a></div><div class="navbar-item"><a class="external-link" href="https://gitee.com/Francis-xsc/francis-xsc" rel="noopener noreferrer" target="_blank" aria-label="Gitee"><!--[--><!--]--> Gitee <span><svg class="external-link-icon" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path><polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg><span class="external-link-icon-sr-only">open in new window</span></span><!--[--><!--]--></a></div><!--]--></nav><!--[--><!--]--><ul class="sidebar-items"><!--[--><li><a href="/program/Java.md" class="sidebar-item sidebar-heading collapsible" aria-label="Java"><!--[--><!--]--> Java <!--[--><!--]--></a><!----></li><li><p tabindex="0" class="sidebar-item sidebar-heading collapsible">Python <span class="right arrow"></span></p><ul style="display:none;" class="sidebar-item-children"><!--[--><li><a href="/program/python.html" class="sidebar-item" aria-label="python-北理工"><!--[--><!--]--> python-北理工 <!--[--><!--]--></a><!----></li><!--]--></ul></li><li><p tabindex="0" class="sidebar-item sidebar-heading collapsible">Markdown <span class="right arrow"></span></p><ul style="display:none;" class="sidebar-item-children"><!--[--><li><a href="/program/Markdown.html" class="sidebar-item" aria-label="Markdown"><!--[--><!--]--> Markdown <!--[--><!--]--></a><!----></li><!--]--></ul></li><!--]--></ul><!--[--><!--]--></aside><!--]--><!--[--><main class="page"><!--[--><!--]--><div class="theme-default-content"><!--[--><!--]--><div><p>牛客小白月赛1的C题</p><blockquote><p>链接：https://ac.nowcoder.com/acm/contest/85/C 来源：牛客网</p><p>毕竟是元宵节，晚上还是要吃几个元宵。 Etéreo 家可是个大家庭，元宵的数量，甚至是餐具的数量，都多的惊人。现在，爱数学的 Etéreo 又来问你有趣的数学题了，快来秒掉它！ Etéreo 家里有 ς 种元宵馅， ϑ 种元宵皮，每个元宵可以选择任意一种元宵馅和任意一种元宵皮。同时有ϖ 张桌子，每张桌子上放了 ϱ 只碗，每只碗能放一只元宵。每只碗都要装一只元宵。Etéreo 会告诉你 ς,ϑ,ϖ,ϱ 的值，想请问你有多少种装元宵的方式。答案对Λ 取模。 两种方式被认为是不同的当且仅当至少有一只碗存在于两种方式的同一个位置但是里面有至少一个元宵不同。 两个元宵被认为是不同的当且仅当元宵馅不同或者元宵皮不同。 碗和桌子都是有编号的，但是你不能改变碗或桌子的编号。 你可以认为碗和桌子都是固定的，你只能改变元宵的种类和位置。</p><p>0≤ς,ϑ≤10<sup>18</sup> 0≤ϖ,ϱ≤10<sup>6</sup> 1≤Λ≤1,000,000,007</p></blockquote><p>这道题看起来不太难,首先有ϖ*ϱ只碗，元宵一共有ς*ϑ种，所以最后的答案为(ϖ*ϱ)<sup>ς*ϑ</sup>种，再对Λ取模即可</p><p>但是指数的结果是非常大的，没有数据结构能存下，而且指数过大，很有可能会超时，那么如何解决这一问题？</p><p>快速幂</p><p>字面意思，就是快速求幂</p><p>先写一下最简单的求法吧。</p><p>在最开始学习C++时，我们首先接触到的方法是cmath中的pow函数或者循环计算</p><p>例如求2^10</p><div class="language-cpp line-numbers-mode" data-ext="cpp"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;iostream&gt;</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cmath&gt;</span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    cout<span class="token operator">&lt;&lt;</span><span class="token function">pow</span><span class="token punctuation">(</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">10</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><div class="language-cpp line-numbers-mode" data-ext="cpp"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;iostream&gt;</span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">int</span> ans<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span><span class="token number">10</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
        ans<span class="token operator">*=</span><span class="token number">2</span><span class="token punctuation">;</span>
    cout<span class="token operator">&lt;&lt;</span>ans<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>pow方法简单，但是效率比循环要低。</p><p>循环效率也不高，计算一个数字的n次幂，就需要循环n次,复杂度为O(n)。</p><p>做最前面的那道算法题时这两种办法肯定是不行的，如何优化？</p><p>例如求2^8</p><p>2<sup>10</sup></p><p>=2*2*2*2*2*2*2*2*2*2</p><p>=(2*2)*(2*2)*(2*2)*(2*2)*(2*2)</p><p>=4^5</p><p>这时我们需要循环的次数就减少了一半，只需要五次</p><p>这是我们的第一次优化，可以发现，底数变成了原来的平方，指数变成了原来的一半</p><p>如果是10000次循环，经过一次优化就变成了5000次，优化的程度就很大了</p><p>继续这么优化</p><p>4<sup>5</sup>=4<sup>2.5</sup></p><p>就发现一个问题，如果是奇数次，指数除以二之后出现了小数部分，那么如何解决？</p><p>提出来其中的一个，指数又变成了偶数</p><p>4<sup>5</sup>=4<sup>4</sup>*4<sup>1</sup></p><p>那么就可以继续优化了</p><p>4<sup>5</sup>=4<sup>4</sup>*4<sup>1</sup>=16<sup>2</sup>*4<sup>1</sup>=256<sup>1</sup>*4<sup>1</sup></p><p>所以这个算法的思路是</p><p>首先与循环算法一样，定义一个结果变量result=1</p><p>如果指数是偶数，那么底数平方，指数除以2</p><p>如果指数是奇数，那么提出来其中一项并乘进结果中，指数减一 复杂度为O(logn)</p><p>代码如下</p><div class="language-cpp line-numbers-mode" data-ext="cpp"><pre class="language-cpp"><code>	<span class="token keyword">long</span> <span class="token keyword">long</span> <span class="token function">fastpow1</span><span class="token punctuation">(</span><span class="token keyword">long</span> <span class="token keyword">long</span> base<span class="token punctuation">,</span><span class="token keyword">long</span> <span class="token keyword">long</span> power<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">int</span> result <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span>power<span class="token operator">&gt;</span><span class="token number">0</span><span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>power<span class="token operator">%</span><span class="token number">2</span><span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                base<span class="token operator">=</span>base<span class="token operator">*</span>base<span class="token punctuation">;</span>
                power<span class="token operator">/=</span><span class="token number">2</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token keyword">else</span>
            <span class="token punctuation">{</span>
                result<span class="token operator">*=</span>base<span class="token punctuation">;</span>
                power<span class="token operator">--</span><span class="token punctuation">;</span>
               	<span class="token comment">//此时power变为偶数，可以进行与power为偶数时相同的操作</span>
                power<span class="token operator">/=</span><span class="token number">2</span><span class="token punctuation">;</span>
                base<span class="token operator">=</span>base<span class="token operator">*</span>base<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> result<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>可以看到，有相同的代码语句，所以进行如下缩减</p><div class="language-cpp line-numbers-mode" data-ext="cpp"><pre class="language-cpp"><code><span class="token keyword">long</span> <span class="token keyword">long</span> <span class="token function">fastpow2</span><span class="token punctuation">(</span><span class="token keyword">long</span> <span class="token keyword">long</span> base<span class="token punctuation">,</span><span class="token keyword">long</span> <span class="token keyword">long</span> power<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">int</span> result <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>power<span class="token operator">&gt;</span><span class="token number">0</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>power<span class="token operator">%</span><span class="token number">2</span><span class="token punctuation">)</span>		<span class="token comment">//如果power为奇数</span>
        <span class="token punctuation">{</span>
            result<span class="token operator">*=</span>base<span class="token punctuation">;</span>
            power<span class="token operator">--</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        power<span class="token operator">/=</span><span class="token number">2</span><span class="token punctuation">;</span>
        base<span class="token operator">=</span>base<span class="token operator">*</span>base<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> result<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>因为power为整数类型，如果为奇数可以自动舍去0.5</p><p>例如power=3，power/2结果为1，与power--;power/=2;结果相同</p><p>所以继续优化</p><div class="language-cpp line-numbers-mode" data-ext="cpp"><pre class="language-cpp"><code><span class="token keyword">long</span> <span class="token keyword">long</span> <span class="token function">fastpow3</span><span class="token punctuation">(</span><span class="token keyword">long</span> <span class="token keyword">long</span> base<span class="token punctuation">,</span><span class="token keyword">long</span> <span class="token keyword">long</span> power<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">int</span> result <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>power<span class="token operator">&gt;</span><span class="token number">0</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
    	<span class="token keyword">if</span><span class="token punctuation">(</span>power<span class="token operator">%</span><span class="token number">2</span><span class="token punctuation">)</span>
    		result<span class="token operator">*=</span>base<span class="token punctuation">;</span>
        power<span class="token operator">/=</span><span class="token number">2</span><span class="token punctuation">;</span>
    	base<span class="token operator">=</span>base<span class="token operator">*</span>base<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> result<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>前面说到，指数的结果非常大，所以常用到取模运算</p><p>这里用到性质</p><p>(a*b)%c=(a%c*b%c)%c</p><p>所以代码如下：</p><div class="language-cpp line-numbers-mode" data-ext="cpp"><pre class="language-cpp"><code><span class="token keyword">long</span> <span class="token keyword">long</span> <span class="token function">fastpow4</span><span class="token punctuation">(</span><span class="token keyword">long</span> <span class="token keyword">long</span> base<span class="token punctuation">,</span><span class="token keyword">long</span> <span class="token keyword">long</span> power<span class="token punctuation">,</span><span class="token keyword">int</span> mod<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">int</span> result <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>power<span class="token operator">&gt;</span><span class="token number">0</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
    	<span class="token keyword">if</span><span class="token punctuation">(</span>power<span class="token operator">%</span><span class="token number">2</span><span class="token punctuation">)</span>
    		result<span class="token operator">=</span><span class="token punctuation">(</span>result<span class="token operator">*</span>base<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
        power<span class="token operator">/=</span><span class="token number">2</span><span class="token punctuation">;</span>
    	base<span class="token operator">=</span><span class="token punctuation">(</span>base<span class="token operator">*</span>base<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> result<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>这大概就是最终的写法了，但是其中的一些地方我们可以改为位运算，速度更快</p><div class="language-cpp line-numbers-mode" data-ext="cpp"><pre class="language-cpp"><code><span class="token keyword">long</span> <span class="token keyword">long</span>  <span class="token function">fastPower5</span><span class="token punctuation">(</span><span class="token keyword">long</span> <span class="token keyword">long</span>  base<span class="token punctuation">,</span> <span class="token keyword">long</span> <span class="token keyword">long</span>  power<span class="token punctuation">,</span> <span class="token keyword">long</span> <span class="token keyword">long</span>  mod<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">long</span> <span class="token keyword">long</span>  result <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token keyword">while</span> <span class="token punctuation">(</span>power <span class="token operator">&gt;</span> <span class="token number">0</span><span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">if</span> <span class="token punctuation">(</span>power <span class="token operator">&amp;</span> <span class="token number">1</span><span class="token punctuation">)</span>			<span class="token comment">//如果power为奇数</span>
			result <span class="token operator">=</span> <span class="token punctuation">(</span>result <span class="token operator">*</span> base<span class="token punctuation">)</span> <span class="token operator">%</span> mod<span class="token punctuation">;</span>
		power <span class="token operator">&gt;&gt;=</span> <span class="token number">1</span><span class="token punctuation">;</span>
		base <span class="token operator">=</span> <span class="token punctuation">(</span>base <span class="token operator">*</span> base<span class="token punctuation">)</span> <span class="token operator">%</span> mod<span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">return</span> result<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>总结一下</p><p>pow效率较低，但是适用于指数为小数的情况</p><p>否则不建议使用</p><p>循环复杂度为O(n),快速幂算法复杂度为O(logn)</p><p>指数越大，效果越明显</p><p>回到分元宵的问题</p><p>最大的坑是输入的四个数据可能有0，需要单独判断，否则通过率为98%。</p><p>最后，题目的答案</p><div class="language-cpp line-numbers-mode" data-ext="cpp"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;iostream&gt;</span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
<span class="token keyword">typedef</span> <span class="token keyword">long</span> <span class="token keyword">long</span> ll<span class="token punctuation">;</span>
ll A<span class="token punctuation">;</span>
ll <span class="token function">fastPower</span><span class="token punctuation">(</span>ll base<span class="token punctuation">,</span> ll power<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	ll c<span class="token punctuation">,</span> o<span class="token punctuation">,</span> w<span class="token punctuation">,</span> e<span class="token punctuation">;</span>
	cin <span class="token operator">&gt;&gt;</span> c <span class="token operator">&gt;&gt;</span> o <span class="token operator">&gt;&gt;</span> w <span class="token operator">&gt;&gt;</span> e <span class="token operator">&gt;&gt;</span> A<span class="token punctuation">;</span>
	<span class="token keyword">if</span> <span class="token punctuation">(</span>c <span class="token operator">==</span> <span class="token number">0</span> <span class="token operator">||</span> o <span class="token operator">==</span> <span class="token number">0</span> <span class="token operator">||</span> w <span class="token operator">==</span> <span class="token number">0</span> <span class="token operator">||</span> e <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		cout <span class="token operator">&lt;&lt;</span> <span class="token number">0</span><span class="token punctuation">;</span>
		<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	cout <span class="token operator">&lt;&lt;</span> <span class="token function">fastPower</span><span class="token punctuation">(</span><span class="token function">fastPower</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token punctuation">(</span>c <span class="token operator">%</span> A<span class="token punctuation">)</span> <span class="token operator">*</span> <span class="token punctuation">(</span>o <span class="token operator">%</span> A<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">%</span> A<span class="token punctuation">,</span> w<span class="token punctuation">)</span><span class="token punctuation">,</span> e<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
ll <span class="token function">fastPower</span><span class="token punctuation">(</span>ll base<span class="token punctuation">,</span> ll power<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	ll result <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token keyword">while</span> <span class="token punctuation">(</span>power <span class="token operator">&gt;</span> <span class="token number">0</span><span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">if</span> <span class="token punctuation">(</span>power <span class="token operator">&amp;</span> <span class="token number">1</span><span class="token punctuation">)</span>
			result <span class="token operator">=</span> <span class="token punctuation">(</span>result <span class="token operator">*</span> base<span class="token punctuation">)</span> <span class="token operator">%</span> A<span class="token punctuation">;</span>
		power <span class="token operator">&gt;&gt;=</span> <span class="token number">1</span><span class="token punctuation">;</span>
		base <span class="token operator">=</span> <span class="token punctuation">(</span>base <span class="token operator">*</span> base<span class="token punctuation">)</span> <span class="token operator">%</span> A<span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">return</span> result<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div></div><!--[--><!--]--></div><footer class="page-meta"><div class="meta-item edit-link"><a class="external-link meta-item-label" href="https://gitee.com/Francis-xsc/francis-xsc/edit/main/program/快速幂算法 牛客小白月赛 1-C分元宵.md" rel="noopener noreferrer" target="_blank" aria-label="Edit this page"><!--[--><!--]--> Edit this page <span><svg class="external-link-icon" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path><polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg><span class="external-link-icon-sr-only">open in new window</span></span><!--[--><!--]--></a></div><div class="meta-item last-updated"><span class="meta-item-label">最后更新时间: </span><!----></div><div class="meta-item contributors"><span class="meta-item-label">Contributors: </span><span class="meta-item-info"><!--[--><!--[--><span class="contributor" title="email: 920364365@qq.com">Francis-xsc</span><!----><!--]--><!--]--></span></div></footer><!----><!--[--><!--]--></main><!--]--></div><!----><!--]--></div>
    <script type="module" src="/assets/app-6c74e544.js" defer></script>
  </body>
</html>
